package com.k.leetcode.linklist.one;

import com.k.leetcode.linklist.LinkNode;

import java.util.Stack;

/**
 * 链表结构 操作
 */
public class Test {
    public static void main(String[] args) {
        LinkNode linkNode3 = new LinkNode();
        linkNode3.value=3;
        linkNode3.next =null;

        LinkNode linkNode2 = new LinkNode();
        linkNode2.value=2;
        linkNode2.next =linkNode3;

        LinkNode linkNode1 = new LinkNode();
        linkNode1.value=1;
        linkNode1.next =linkNode2;

//        printLinkNode(linkNode1);

        // reverse linklist
//        LinkNode r = reverseLinkNode(linkNode1);
//        printLinkNode(r);

//        LinkNode r1 = reverseLinkNode1(linkNode1);
//        printLinkNode(r1);

        reverseLinkNode2(linkNode1);
    }
    private static void printLinkNode(LinkNode head){
        // 迭代链表
        LinkNode curr = head;
        while (curr!=null){
            int value = curr.value;
            System.out.println(value);
            curr = curr.next;
        }
    }

    /**
     * 迭代
     * @param head head
     * @return LinkNode
     */
    private static LinkNode reverseLinkNode(LinkNode head){
        LinkNode curr = head;
        LinkNode pre = null;
        while (curr!=null){
            // 保存下个节点,否则下步骤会断链
            LinkNode next = curr.next;
            // 断链
            curr.next = pre;
            //
            pre = curr;

            curr = next;
        }
       return pre;
    }

    /**
     * 递归
     * @param head head
     * @return LinkNode
     */
    private static LinkNode reverseLinkNode1(LinkNode head){
        if(head==null || head.next==null){
            return head;
        }
        LinkNode newHead = reverseLinkNode1(head.next);
        LinkNode cur = head.next;
        cur.next= head;
        head.next = null;
        return  newHead;
    }

    /**
     * 栈结构
     * @param head head
     */
    private static void reverseLinkNode2(LinkNode head){
        Stack<LinkNode> stack = new Stack<>();
        LinkNode curr = head;
        while (curr!=null){
            stack.push(curr);
            curr = curr.next;
        }
        while (!stack.isEmpty()){
            System.out.println(stack.pop().value);
        }
    }
}
